# Full text of "Cluster synchronization in networks of coupled non-identical dynamical systems"

## See other formats

Cluster synchronization in networks of coupled non-identical dynamical systems Wenlian Li|] Centre for Computational Systems Biology, Fudan University, Shanghai, P. R. China Bo LiuQ and Tianping Cheijil Shanghai Key Laboratory for Contemporary Applied Mathematics, School of Mathematical Sciences, Fudan University, Shanghai, P. R. China (Dated: December 12, 2009) Abstract In this paper, we study cluster synchronization in networks of coupled non-identical dynamical systems. The vertices in the same cluster have the same dynamics of uncoupled node system but the uncoupled node systems in different clusters are different. We present conditions guaranteeing cluster synchronization and investigate the relation between cluster synchronization and the unweighted graph topology. We indicate that two condition play key roles for cluster synchronization: the common inter-cluster coupling condition and the intra-cluster communication. From the latter one, we interpret the two well-known cluster synchro- nization schemes: self-organization and driving, by whether the edges of communication paths lie at inter- or intra-cluster. By this way, we classify clusters according to whether the set of edges inter- or intra-cluster edges are removable if wanting to keep the communication between pairs of vertices in the same cluster. Also, we propose adaptive feedback algorithms on the weights of the underlying graph, which can synchro- nize any bi-directed networks satisfying the two conditions above. We also give several numerical examples to illustrate the theoretical results. PACS numbers: 05.45.Gg, 05.45.Xt, 02.30.Hq *Electronic address: wenlian@fudan.edu.cnl ^Electronic address: 071018024@fudan.eduxn| ^Electronic address: tchen@fudan.edu.cnl 1 Cluster synchronization is considered to be more momentous than complete synchroniza- tion in brain science and engineering control, ecological science and communication engi- neering, social science and distributed computation. Most of the existing works only fo- cused on networks with either special topologies such as regular lattices or coupled two/three groups. For the general coupled dynamical systems, theoretical analysis to clarify the rela- tionship between the (unweighted) graph topology and the cluster scheme, including both self-organization and driving, is absent. In this paper, we study this topic and find two es- sential conditions for an unweighted graph topology to realize cluster synchronization: the common inter-cluster coupling condition and the intra-cluster communication. Thus under these conditions, we present two manners of weighting to achieve cluster synchronization. One is adding positive weights on each edges with keeping the invariance of the cluster syn- chronization manifold and the other is an adaptive feedback weighting algorithms. We prove the availability of each manner. From these results, we give an interpretation of the two clus- tering synchronization schemes: self-organization and driving, involved with the unweighted graph topology, via the communication between pairs of individuals in the same cluster. Thus, we present one way to classify the clusters via whether the set of inter- or intra-cluster edges are removable if still wanting to keep the communication between vertices in the same cluster. I. INTRODUCTION Recent decades witnesses that chaos synchronization in complex networks has attracted in- creasing interests from many research and application fields [ 1, 2, sl], since it was firstly introduced in Ref. I^l. Word "synchronization" comes from Greek, which means "share time" and today, it comes to be considered as "time coherence of different processes". Many new synchronization phenomena appear in a wide range of real systems, such as biology tSJ, neural networks phys- iological processes |17|]. Among them, the most interesting cases are complete synchronization, cluster synchronization, phase synchronization, imperfect synchronization, lag synchronization, and almost synchronization etc. See Ref. M\ and the references therein. Complete synchronization is the most special one and characterized by that all oscillators ap- proach to a uniform dynamical behavior. In this situation, powerful mathematical techniques from dynamical systems and graph theory can be utilized. Pecora et.al. [|9(] proposed the Master Stabil- 2 ity Function for transverse stability analysis [lOj of the diagonal synchronization manifold. This method has been wide system lUl]. Refs. [112, y used to study local completer synchronization in networks of coupled 13 proposed a framework of Lyapunov function method to investigate global synchronization in complex networks. One of the most important issues is how the graph topology affects the synchronous motion [2]. As pointed out in Ref. [15], the connectivity of the graph plays a significant role for chaos synchronization. Cluster synchronization is considered to be more momentous in brain science I16I1 and engi- neering control 1 17], ecological science llisll and communication engineering [19], social science 1201] and distributed computation [21]. This phenomenon is observed when the oscillators in net- works are divided into several groups, called clusters, by the way that all individuals in the same cluster reach complete synchronization but the motions in different clusters do not coincide. Clus- ter synchronization of coupled identical systems are studied in Refs. 11221 |2j, |24|, |25|]. Among them, Jalan et. al. 11251] pointed out two basic formations which realize cluster synchronization. One is self-organization, which leads to cluster with dominant intra-cluster couplings, and the other is driving, which leads to cluster with dominant inter-cluster couplings. Nowadays, the interest of cluster synchronization is shifting to networks of coupled non- identical dynamical systems. In this case, cluster synchronization is obtained via two aspects: the oscillators in the same cluster have the same uncoupled node dynamics and the inter- or intra-cluster interactions realize cluster synchronization via driving or/and self-organizing con- figurations. Refs. [|23l] proposed cluster synchronization scheme via dominant intra-couplings and common inter-cluster couplings. Ref. [|26l] studied local cluster synchronization for bipartite systems, where no intra-cluster couplings (driving scheme) exist. Refs. 1271 ] investigated global cluster synchronization in networks of two clusters with inter- and intra-cluster couplings. Belykh et. al. studied this problem in ID and 2D lattices of coupled identical dynamical systems in Ref. ll22|] and non-identical dynamical systems in Ref. 11281] . where the oscillators are coupled via inter- or/and intra-cluster manners. Ref. 1291] used nonlinear contraction theory |130(] to build up a suf- ficient condition for the stability of certain invariant subspace, which can be utilized to analyze cluster synchronization (concurrent synchronization is called in that literature). However, up till now, there are no works revealing the relationship between the (unweighted) graph topology and the cluster scheme, including both self-organization and driving, for general coupled dynamical systems. The purpose of this paper is to study cluster synchronization in networks of coupled non- 3 identical dynamical systems with various graph topologies. In Section 2, we formulate this prob- lem and study the existence of the cluster synchronization manifold. Then, we give one way to set positive weights on each edges and derive a criterion for cluster synchronization. This criterion implies that the communicability between each pair of individuals in the same cluster is essential for cluster synchronization. Thus, we interpret the two communication schemes: self-organization and driving, according to the communication scheme among individuals in the same cluster. By this way, we classify clusters according to the manner by which synchronization in a cluster real- izes. In Sec. 3, we propose an adaptive feedback algorithms on weights of the graph to achieve a given clustering. In Sec. 5, we discuss the cluster synchronizability of a graph with respect to a given clustering and present the general results for cluster synchronization in networks with general positive weights. We conclude this paper in Sec. 6. n. CLUSTER SYNCHRONIZATION ANALYSIS In this section, we study cluster synchronization in a network with weighted bi-directed graph and a given division of clusters. We impose the constraints on graph topology to guarantee the invariance of the corresponding cluster synchronization manifold and derive the conditions for this invariant manifold to be globally asymptotically stable by the Lyapunov function method. Before that, we should formulate the problem. Throughout the paper, we denote a positive definite matrix Zhy Z > and similarly for Z < 0, Z <0, and Z >0. We say that a matrix Z is positive definite on a linear subspace V if u^Zu > for 3A\ u E V and u 0, denoted hy Z\v > 0. Similarly, we can define Z\v < 0, Z\v > 0, and Z\v < 0. If a matrix Z has all eigenvalues real, then we denote by Xk{Z) the k-th largest eigenvalues of Z. Z^ denotes the transpose of the matrix Z and Z^ = {Z + Z~^)/2 denotes the symmetry part of a square matrix Z. j^A denotes the number of the set A with finite elements. A. Model description and existence of invariant cluster synchronization manifold A bi-directed unweighted graph Q is denoted by a double set {y,£}, where V is the vertex set numbered by {1, • • • , m}, and £ denotes the edge set with e{i, j) E £ if and only if there is an edge connecting vertices j and i. AA(i) = {j e V : e(i, j) e £} denotes the neighborhood set of vertex i. The graph considered in this paper is always supposed to be simple (without self- 4 loops and multiple edges) and bi-directed. A clustering C is a disjoint division of the vertex set V: C = {Ci, C2, ■ ■ ■ , Ck} satisfying (i). Uf=i Ck = V; (ii). ^ fl = holds for k^l. The network of coupled dynamical system is defined on the graph Q. The individual uncoupled system on the vertex i is denoted by an n-dimensional ordinary differential equation = fk{x^) for all i E Ck, where x"^ = [x\, ■ ■ ■ , x^]^ is the state variable vector on vertex i and fk{-) : IR" — > is a continuous vector-valued function. Each vertex in the same cluster has the same individual node dynamics. The interaction among vertices is denoted by linear diffusion terms. It should be emphasized that fk for different clusters are distinct, which can guarantee that the trajectories are apparently distinguishing when cluster synchronization is reached. Consider the following model of networks of linearly coupled dynamical system 113 ill = fkix') + J2 -x'), teCk, k = l,--- ,K. (1) j&j\r{i) where Wij is the coupling weight at the edge from vertex j to i and T = ['juv]u,v=i denotes the inner connection by the way that juv 7^ if the the u-th component of the vertices can be influenced by the t>-th component. The graph Q is bi-directed and the weights are not requested to be symmetric. Namely, we don't request Wij = Wji for each pair (i, j) with e(i, j) E £. Let A = [aij]"'j^^ be the adjacent matrix of the graph Q. That is, = 1 if e{i,j) E £; = otherwise. Then, model ([T]) can be rewritten as m x' = fk{x') + a,jWi.jr{x^ -x'), iECk, k = !,■■■ ,K. (2) In this paper, cluster synchronization is defined as follows: 1 . The differences among trajectories of vertices in the same cluster converge to zero as time goes to infinity, i.e., \im[x\t) -x^{t)] = 0,\/i,j ECk, k = !,■■■ ,K; (3) 2. The differences among the trajectories of vertices in different clusters do not converge to zero, i.e., limt^oo|a^*'(^) — x^' {t)\ > holds for each i' E Ck and j' E Ci with k ^ I. As mentioned above, we suppose that the latter one can be guaranteed by the incoincidence of /fc(-). Under this prerequisite assumption, cluster synchronization is equivalent to the asymptotical stability of the following cluster synchronization manifold with respect to the clustering C: Sc{n) = {[x^^ , ■ ■ ■ x' = x^ eW, ^i,jECk, k = l,--- ,K}. (4) To investigate cluster synchronization, a prerequisite requirement is that the manifold Sc{n) should be invariant through Eqs. Assume that a;*(t) = s'^(t) for each z G is the synchronized solution of the cluster Ck, k = 1, ■ ■ ■ , K. By Eqs. Q, each s'^ must satisfy K where Oi^k' = Y.jeCy (^ij'^ij- This demands ai^^k' = ai2,k' for any ii G Ck, 12 G Ck, namely, ai^k' is independent of i. Therefore, we have This condition is sufficient and necessary for the cluster synchronization manifold Sc{n) is invari- ant through the coupled system Q for general maps /fc(-). Denote Mk'ii) = -^(i) f]Ck', and define an index set C]. = {k' : k' k, and Nk'{i) 7^ 0}. The set Cl represents those clusters other than Ck and have links to the vertex i. To satisfy the condition Q, the following common inter-cluster coupling condition over the unweighted graph topology should be satisfied: for A; = 1, ■ ■ ■ , i^. Therefore, we can use Ck to represent CI for all i E Ck ii the common inter-cluster coupling condition is satisfied. Throughout this paper, we assume that the vector- valued function /^(x) — aTx : M" satisfies decreasing condition for some a G M. That is, there exists 5 > such that holds for all ^ This condition holds for any globally Lipschitz continuous function /(■) for sufficiently large a > and F = /„. However, even though / (■) is only locally Lipschitz, if the solution of the coupled system ^ is essentially bounded, then restricted to such bounded region, the condition dS]) also holds for sufficiently large a and F = /„. In this paper, we suppose that the solution of the coupled system ^ is essentially bounded. ai^k' = a{k, k'), i e Ck, k ^ k' . (6) 4 = 4, vz,z'gc,. (7) (8) 6 B. Cluster synchronization analysis In the following, we investigate cluster synchronization of networks of coupled non-identical dynamical systems withe the following weighting scheme: f /- J G Afk{i) andAfkii) G Wij = < (9) I otherwise, where di^k' = #A/'fc(i) denotes the number of elements in Nk'{i) and c denotes the coupling strength.. Thus, the coupled system becomes: = fk{x") + c E E r(x^ --') ieCk,k = l,--- ,K. (10) It can be seen that in Eqs. (flOl) . for each i G Ck, the corresponding Ui^y = c for all k' G Ck under the common inter-cluster coupling condition. The general situation can be handled by the same approach and will be presented in the discussion section. We denote the weighted Laplacian of the graph as follows. For each pair (i, j) with i ^ j, Uj = ^ if j G Mkii) and A4(0 7^ for some k G {1, ■ ■ ■ -.K}, and lij = otherwise; Ui = — Zljli ^ij- Thus, Eqs. (flOl) can be rewritten as: m x' = fk{x') + cY,h3^x\ leCk, k = l,--- ,K. (11) i=i The approach to analyze cluster synchronization is extended from that used in Ref . /l4^ to study complete synchronization. Let d = [di, - ■ ■ , dm]^ be a vector with di > for alH = 1, ■ ■ ■ ,m. We use the vector d to construct a (skew) projection of x = [x^^, ■ ■ ■ , x'"^]^ onto the cluster synchronization manifold Sc{n). Define an average state with respect to d in the cluster Ck as = — ^ ] diX . Thus, we denote the projection of x on the cluster synchronization manifold Sc{n) with respect to d as: Xd = [x^^ , ■ ■ ■ > i"^ ]^ is denoted as: x' = x^, ifi G Ck. Then, the variations x* — x^ compose the transverse space: Tc\n) = lu = [u^^,--- gM™" : G M", ^rf^M* = 0, V = 1, ■ • • , 7^1. In particular, in the case of n = 1, it denotes u = \u u : ^ diU^ 0, VA; K From the definition, we have the following lemma which is repeatedly used below. Lemma 1 For each k ^ 1, - ■ ■ ,K, it holds ^di{x' - x^) = 0. In fact, note 0. The lemma immediately follows. As a direct consequence, we have Jk = for any Jk, with a proper dimension, independent of the index i. Since the dimension of T^{n) is n{m — fC), the dimension of Sc is nK, and 5c('^) is disjoint with T^{n) except the origin, M™" = Sc{n) T^{n), where denotes the direct sum of linear subspaces. With these notations, the cluster synchronization is equivalent to the transverse stability of the cluster synchronization manifold Sc{n), i.e., the projection of x on the transverse space T^{n) converges to zero as time goes to infinity. Theorem 1 Suppose that the common inter-cluster coupling condition holds, T is symmetry and nonnegative definite, and each vector-valued function fk{-) — «r- satisfies the decreasing condition ((S]) for some a G M. //" there exists a positive definite diagonal matrix D such that the restriction of [D{cL + aIm)Y, restricted to the transverse space Tq{1), is non-positive definite. I.e., D{cL + air, < (12) ri*(i) holds, then the coupled system ([77]) can clustering synchronize with respect to the clustering C. Proof. We define an auxiliary function to measure the distance from x to the cluster synchroniza- tion manifold as follows 1 ^ Differentiating Vk along Eqs. (fTTI) gives X' Recalling the definitions of Uj and the common inter-cluster coupling condition ([7]), we have kj = ^ k'j, Ck, k ^ k', (13) which leads By Lemma [B we have (14) y^^djjx ieCk ieCk due to the facts ( 13 and m. Vk = ^di{x' i€Ck fk{x = ^di{x' i€Ck fk{x 0, J]t/,(x^-x^)Vfc(a:^)=0, J^/.^Tx^') =0, A;' = 1,.--,K, fc'=i ieCfc, fc'=i jeCfc, From the decreasing condition ([8]): {w - vy[fk{w) - fk{v) - ar{w - v)] < -6{w - vy{w - v), we have Vk < K ieCk '- k'=lj£Cy Thus, K V < -5^^di{x' - k=i ieCk K x^dY {x' - X^'d) K E J]/,,r(x^ -x^') + ar(x^-, k' = lj&Cy k=l ieCk K -5 E XI ~ ' {x' - x'^) + {x-Xd)' { [D{cL + alm)\ ' ®T\{x~Xd) k=i ieCk where denotes the Kronecker product and D = diag[(ii, ■ ■ ■ , dm\ It is clear that [D{cL + aIm)y < 0. Decompose TJ*(n) < Oimplies {[D{cL + aIm)Y®In} the positive definite matrix F as F = C^C for some matrix C and let y = [y^ , ■ " " ? y'^^Y with = C(x* — x^) for all i E Ck, i.e., y = (Im C){x — Xd). By Lemma 1, it is easy to see that J2ieCk '^^y^ ^ ^ieCfc diC{x^ — ^d) = 0- This implies that ?/ G T^{n). Therefore, (x - Xd)^| [L)(cL + a/m)]'' ® f|(x - Xd) = (X - Xd)^ (im ® C^) { [/^(CL + aim)] ' ® /„} (/m ® C) (X - Xd) = [D(cL + aIm)Y® Ir]y< 0. (15) Hence, we have V < -5{x - Xd)^{D ® /„)(x - Xd) = -25 X V. This implies that V{t) < exp(— 25 t)V'(O). Therefore, limf^oo V'(t) = 0. Namely. \im.t^oo[x{t) — Xd{t)] = holds. In other words, lim^^ooi^;* ~ ^dl — ^ each i E Ck and k = 1, - ■ ■ ,K. According to the assumption that fk(-) are so different that if cluster synchronization is realized, the clusters are also different, we are safe to say that the coupled system ([TT]) can clustering syn- chronize. □ If each uncoupled system x* = fk{x^) is unstable, in particular, chaotic, a must be positive in the inequality ([8]). It is natural to raise the question: can we find some positive diagonal matrix D such that (fT2l) satisfies with sufficiently large c and some certain a > 0. In other words, for the coupled system (flOl) , what kind of unweighted graph topology Q satisfying the common inter- cluster condition ^ can be a chaos cluster synchronizer with respect to the clustering C. It can be seen that if the restriction of {DL + D) to the transverse subspace T(f(l) is negative, i.e., (DL + 1^.(1) <0 (16) holds, then Ineq. (fT2l) holds for sufficiently large c. With these observations, we have Theorem 2 Suppose that the common inter-cluster coupling condition (0) holds for the coupled system ([77]), and a > 0. There exist a positive diagonal matrix D and a sufficiently large constant c such that Ineq. ([72]) holds if and only if all vertices in the same cluster belong to the same connected component in the graph Q. 10 Proof. We prove the sufficiency for connected graph and unconnected graph separated. Case 1: The graph Q is connected. Then, L is irreducible. Perron-Frobenius theorem (see Ref. [32] for more details) tells that the left eigenvector [^i, ■ ■ ■ , ^m]^ of L associated with the eigenvalue has all components > 0, i = 1, ■ ■ ■ ,m. In this case, we pick di = ^i, i = 1, ■ ■ ■ ,m. And its symmetric part [DLY = (DL + L^D)/2 has all row sums zero and irreducible with \i{[DLY) = associated with the eigenvector e = [1, ■ ■ ■ , 1]^ and \2{[DLY) < 0. Therefore, vJ {DL)u < \2{DLYu^ u < for any m 7^ satisfying e = 0. Now, for any u = [ui, ■ ■ ■ , Um]^ E M™ with u^d = 0, define u = [u, ■ ■ ■ , u]'^ , where u = ^ YliLi Wi- It is clear that DLu = and vYDL = and {u — M)^e = 0. Therefore, m u ' {DL + V D)u = {u- uY{DL + V D){u-u) <Q since both hold. This implies Ineq. (1161) holds. Case 2: The graph Q is disconnected. In this case, we can divide the bigraph Q into several connected components. If all vertices belongs to the same cluster are in the same connected component, then by the same discussion done in case 1, we conclude that Ineq. (fT6l) holds for some positive definite diagonal matrix D. Necessity. We prove the necessity by reduction to absurdity. Considering an arbitrary discon- nected graph Q, without loss of generality, supposing that L has form: Li L2 and letting Vi and V2 correspond to the sub-matrices Li and L2 respectively, we assume that there exists a cluster Ci satisfying Ci Vj 7^ for alH = 1,2. That is, there exists at least a pair of vertices in the cluster Ci which can not access each other. For each d = [rfi, ■ ■ ■ , rfm]^ with rfj > for alH = 1, ■ ■ ■ , m, letting D = diag[(ii, • • ■ , rfm], we can find a nonzero vector u G T^{1) such that DLu = (see the Appendix for the details). This implies that inequality (fT6l) does not hold. So, inequality (fT2l) can not hold for any positive a. □ In the case that the clustering synchronized trajectories are chaotic, with a > 0, Theorem[2]tells us that chaos cluster synchronization can be achieved (for sufficiently large coupling strength) if and only if all vertices in the same cluster belongs to the same connected component in the graph g. In summary, the following two conditions play the key role in cluster synchronization. 11 1 . Common inter-cluster edges for each vertex in the same cluster; 2. Communicability for each pair of vertices in the same cluster. The first condition guarantees that the clustering synchronization manifold is invariant through the dynamical system with properly picked weights and the second guarantees that chaos clustering synchronization can be reached with a sufficiently large coupling strength. C. Schemes to clustering synchronize The theoretical results in previous section indicate that the communication among vertices in the same cluster is important for chaos cluster synchronization. A cluster is said to be commu- nicable if every vertex in this cluster can connect any other vertex by paths in the global graph. These paths between vertices are composed of edges, which can be either of inter-cluster or intra- cluster. Refs. [12511 showed that this classification of paths distinguishes the formation of clusters. A self-organized cluster implies that the intra-cluster edges are dominant for the communications between vertices in this cluster. And, a driven cluster is that the inter-cluster edges are dominant for the communications between vertices in this cluster. There are various of ways to describe "domination". In the following, we consider the unweighted graph topology and investigate the two clustering schemes via the results above. We firstly describe self-organization and driving as two schemes for cluster synchronization. Self-organization represents the scheme that the set of intra-cluster edges are irremovable for the communication between each pair of vertices in the same cluster and driving represents the scheme that the set of inter-cluster edges are irremovable for the communication between vertices in the same cluster. Thus, we propose the following classification of clusters. 1 . Self-organized cluster: the subgraph of the cluster is connected but if removing the intra- cluster links of the cluster, there exist at least one pair of vertices such that no paths in the remaining graph can connect them; 2. Driven cluster: the subgraph of the cluster is disconnected but even if removing all intra- cluster links of the cluster, each pair of vertices in the cluster can reach each other by paths in the remaining graph; 12 TABLE I: Communicability of clusters under edge-removing operations Remove the intra-cluster edges Remove the inter-cluster edges Self-organized cluster no yes Driven cluster yes no Mixed cluster yes yes Hybrid cluster no no 3. Mixed cluster, the subgraph of the cluster is connected and even if removing all intra-cluster links of the cluster, each pair of vertices in the cluster can reach each other by paths in the remaining graph; 4. Hybrid cluster, the subgraph of the cluster is disconnected and if removing the intra-cluster links of the cluster, there exist at least one pair of vertices such that no paths in the remaining graph can link them. Table IJ describes the characteristics of each cluster class. Fig[T]shows examples of these four kinds of clusters, which will be used in later numerical illustrations. With this cluster classification, we conclude that any mixed or self-organized cluster can not access another hybrid or self-organized cluster. Table HI] shows all possibilities of accessibility among all kinds of clusters in a connected graph. Moreover, it should be noticed that the cluster in the networks as illustrated in Fig[T]may not be connected via the subgraph topologies. For example, the white and blue clusters in graph 1, the red and blue clusters in the graph 3, as well as all clusters in graph 2, are not connected by inter-cluster subgraph topologies. Certainly, the vertices in the same cluster are connected via inter- and intra-cluster edges. That is, we can realize cluster synchronization in non-clustered networks. D. Examples In this part, we propose several numerical examples to illustrate the theoretical results. In this example, K = 3. The three graph topologies are shown in Fig. [H The coupled system is J: 7^ Y. = fkix') + c (17) 13 TABLE II: Possibility of coexistence for two kinds of clusters in connected graph Self-organized Driven Hybrid Mixed Self-organized X V X X Driven Hybrid X X Mixed X X where T = diag[l, 1, 0] and fk{-) are non-identical Lorenz systems: 10(m2 - Ml) g fkW) = \ - M2 - U1U3 (18) U1U2 - bkU3, where the parameter bi = 28 for the white cluster, 62 = 38 for the red cluster, and 63 = 58 for the blue cluster. var X As shown in Ref. BSll . the boundedness of the trajectories of an array of coupled Lorenz systems can be ensured. Therefore, the decreasing condition ([8]) is satisfied for a sufficiently large a. We use the following quantity to measure the variation for vertices in the same cluster: where Xk = SieCfc (') denotes the time average. The ordinary differential equations (flTI) are solved by the Runge-Kutta fourth-order formula with a step length 0.01. The time average interval is [50, 100] [1370. Fig. [^indicates that for either graph 1, graph 2, or graph 3, the coupled system (fT71) clustering synchronizes respectively, if the coupling strength is larger than certain threshold value. Instead, for the graph 1, despite the coupled system can synchronize if c is greater than some value (around 10), it can also synchronize if c G [2.2, 5]). It is not very surprising. Previous theoretical results only give sufficient condition that the coupled system can clustering synchronize if the coupling strength c is large enough. It does not exclude the case that the coupled system can still clustering synchronize even if the coupling strength c is small. The following quantity is used to measure the deviation between clusters: dis(t) = min[xi(t) — Xj{t)Y[xi{t) — Xj{t)\ 14 Figl3] shows that the deviation between clusters is apparent, even "var ^ 0". In FigjH the dynamical behaviors for all clusters in certain phase plane are given. Although the attractor for each cluster seems to have similar structure and shape, the positions at same time are still different. It is clear that the difference is caused by the different choice of parameters for different clusters. This illustrates that the cluster synchronization is actually realized. III. ADAPTIVE FEEDBACK CLUSTER SYNCHRONIZATION ALGORITHM For certain network topology which has weak cluster synchronizability, i.e., the threshold to ensure clustering synchronization is relatively large, which is further studied in Sec. IV.A. It is natural to raise the following question: How to achieve cluster synchronization for networks no matter whether they have "good" topology or not. One approach proposed recently is adding weights to vertices and edges. Refs [|34l] showed evidences that certain weighting procedures can actually enhance complete synchronization. On the other hand, adaptive algorithm has emerged as an efficient means of weighting to actually enhance complete synchronizability Ool . In this section, we consider the coupled system fkix') + J2 a^JW^,T{x^ -x'), teCk, k = !,■■■ ,K. (19) and propose an adaptive feedback algorithm to achieve cluster synchronization for a prescribed graph. Suppose that the common inter-cluster and communicability conditions are satisfied. Without loss of generality, we suppose that the graph G is undirected and connected. Consider the coupled system ^ with Laplacian L defined as in Eqs.(fTT1) and (f^ = [di, ■ ■ ■ , dm] is the left eigenvector of L associated with the eigenvalue 0. Now, we propose the following adaptive cluster synchronization algorithm x'{t) = fk{x\t)) + Y.7=i aijWij{t)T[x^{t) - x\t)l teCk, k = l,--- ,K, Wi,{t) = pi,di[x\t) - x\{t)YT[x\t) - x^{t)l (20) for each Cjj G £ and i G C^, A; = 1, ■ ■ ■ with pij > are constants. Theorem 3 Suppose that the graph Q is connected, all the assumptions of Theorem [7] hold, the system d20l) is essential bounded. The system d20l) clustering synchronizes for any initial data. 15 Proof. First of all, pick Uj as defined in Eqs. (fTTI) and a sufficiently large c.Since Q is connected, Theorem 2 tells D{cL + aJ„ Define the following candidate Lyapunov function < 0. (21) A' , Q(x,w) = ^g,. fc=i Differentiating Qfc, we have idCt, ^ j=l ^ K ^^^^^ ^tjC ^Xj d) rf>j T'^\ Similar to the proof of Theorem 1 , we have 5^ 4 = E - ^dV\ Mx') - fix',) + c J2 i&Ci i&d ^ j=l X^ - X^^) and K K Q = 5^ Qfc < -5 5^ 5^ d,{x' - x^)"^(x. - x^) fc=i fc=i ieCfc K k=l i&Ck aT{x' - x',) + c^lijT{x^ - X" -(5(x - Xdy{D ® /)(x - Xd) + (x - Xrf)"^|[D(cL + aI^)Y ® r|(x - x^). Ineq[2n implies Q < -S{x - x^y {D ® /) (x - Xd) < 0. This implies / 6{x{s) - Xd{s)y{D ® /) (x(s) - Xd{s))ds < Q(0) - Q(t) < Q{0) < oo (22) Jo 16 From the assumption of the boundedness of Eq.(l20l). we can conclude \imt^oo[x{t) — Xd{t)] = due to the fact that x{t) is uniform continuous. This completes the proof. □ For the disconnected situation, we can split the graph into several connected components and deal with each connected component by the same means as above. The dynamics of the weights Wij{t) is an interesting issue. Even though it is illustrated in Fig. |7] that all weights converge, to our best reasoning, we can only prove that all intra- weights converge, i.e., vertices i and j belonging to the same cluster Ck- In fact, by (|22l) . we have - x^(r)] [x\t) - xS(r)]rfr < +00. Thus, \Wij{T)\dT = Pijdi dr < I p.,rf,||r|h||[x^(r) -a;^(r)]^[x^(r) -x^(r)]| + \[x' (r) - x'^ir)]" [x^ (r) - x',{t)]\ \dT < P^A\\n2il r[x\r)-x^,{r)Y[x\r)-x',{T)]dT 2 +\ I W{T)-x',{r)Y[x^{r)-x',{r)]dr 2 Therefore, for any e > 0, there exists T > 0, such that for any ti > T,t2 > T, we have \Wij{t2) - Wij{ti)\ < I \Wij{T)\dT < e Jti By Cauchy convergence principle, Wij{t) converges to some final weights w*j for i G Ck, j G Ck when t ^ 00. On the other hand, to our best reasoning, we can not prove whether or not the weights Wij{t) converges, if the vertex i and j belong to different clusters. If we assume the convergence of all weights, according to the the LaSalle invariant principle, the final weights should guarantee that the cluster synchronization manifold is still invariant. That is to say, if difference trajectories: ^fc' _ linearly independent, the cluster the condition (6) still holds for the final weights. Moreover, we have found out that the final weights in our example sensitively depends on the initial values. Fig. [8] gives two sets of weighted topologies of the three graphs as shown in Fig. [T] after employing the adaptive algorithm with two different sets of initial values of Wij{0) and the same parameters. One can see that the final weight can be quite different for different initial values 17 and even be negative. From this observation, we argue that it may be the adaptive process not the final weights counts to reach cluster synchronization. The further investigation of the final weights is out of the scope of the current paper. A. Examples We still use the graphs 1-3 described in Fig{T]and the Lorenz system (fTSl) as the uncoupled sys- tem to illustrate the adaptive feedback algorithms. The ordinary differential equations are solved by the the Runge-Kutta fourth-order formula with a step length 0.01. The initial values of the states and the weights are randomly picked in [—3, 3] and [—5, 5] respectively. We use the follow- ing quantity to measure the state variance inside each cluster with respect to time. k=l ^ ^ i£Ck Figl5] shows that the adaptive algorithm succeeds in clustering synchronizing the network with respect to the pre-given clusters. Figsl6] indicates that the differences between clusters due to non-identical parameters bk- As shown in Fig|71 the weights converge but the limit values are not always positive. This is not surprising. The right-hand side of the algorithm (|20|) can be either positive or negative, which causes some weights of edges to be negative. The situation of negative weights is out of the scope of this paper. rV. DISCUSSIONS In this section, we make further discussions for some interesting relating issues. A. Clustering synchronizability Synchronizability is used to measure the capability of of synchronization for the graph. It can be described by the threshold of the coupling strength to guarantee that the coupled system can synchronize. For com plet e synchronization, it was formulated as a function of the eigenvalues of symmetric Laplacian 111 ill or certain Rayleigh quotient of asymmetric Laplacian lIlSll . How the topology of the underlying graph affects synchronizability is an important issue for the study of complex networks tM- Here, similarly, we are also interested in how to formulate and analyze the cluster-synchronizability of a graph Q and a clustering C. 18 Consider the model (fTTI) of coupled system. Theorem [T] tells us that under the common inter- cluster condition, the cluster synchronization condition (fT2l) can be rewritten as a for some positive definite diagonal D. Therefore, we take the Rayleigh-Hitz quotient L'>JGC=niax mm rp— , to measure the cluster synchronizability for the graph Q and clustering C, where V denotes the set of positive definite diagonal matrices of dimension m. It can be seen that the larger CSg^ is, the smaller the coupling strength c can be such that the coupled system (fTTI) clusteringly synchronize. In particular, if L is symmetric, then CSg^ is just the maximum eigenvalue of —L in the transverse space Tq{1), where e = [1, 1, ■ • ■ , 1]^. It is an interesting topic that how the two schemes (self- organization and driving) affect the cluster synchronizability for a given graph topology and will be a topic in the future. Re-consider the examples in Sec.II.D, we can use Matlab LMI and Control Toolbox to obtain the numerical values of CSg^ for three graphs shown in Fig. [U Thus, we can derive their values: 0.472, 0.178, and 0.172, respectively. Notwithstanding the right-hand of the Lorenz system does not satisfy the decreasing condition globally, as detailed analyzed in Ref. /sS], the trajectory of the coupled Lorenz systems is essentially bounded, of which the bound is independent of the coupling strength c. So, concentrating on the bounded terminal region of all trajectories, the decreasing condition can be satisfied and a can be estimated [40]. Here, we get a ~ 119.3021, 120.9882, and 114.6048, respectively. Thus, we obtain estimations of the infimum of c: 252.795 for the graph 1, 766.892 for the graph 2, and 667.9655 for the graph 3. The details of reasoning and algebras are omitted here. It is clear that they all locate in the region of cluster synchronization as numerically illustrated in fig. [2]but less accurate since the estimations are rather loose. B. Generalized weighted topologies Previous discussions can also be available toward the coupled system ^ with general weights. m = fk{x') + ^ aijW,jT{x^ -x'), ieCk, k = !,■■■ ,K. (24) 19 Here, the graph may be directed, i.e., a^j = 1, if there is an edge from vertex j to vertex i, otherwise, aij = 0. Weights are even not required positive. For the existence of invariant cluster synchronization manifold, we assume E Wi (25) holds for all i, i' G Ck and k ^ k'. Define its Laplacian G = [fifij]™ =i as follows. Wi aij = 1 9ij = < i ^ j and ttij = E 9ik -1= j Thus, Eq. (l24l) becomes + i & Ck, k = l,--- ,K. (26) Replacing ckj by (^jj and following the routine of the proof of theorem [H we can obtain follow- ing result. Theorem 4 Suppose that the common inter-cluster coupling condition d25l) is satisfied, each fk{-) — ^r- satisfies the decreasing condition for some a E M, and T is nonnegative definite. If there exists a positive definite diagonal matrix D such that D{G + ah < (27) ri'(i) holds, then the coupled system can clustering synchronize with respect to the clustering C. And, we use the same discussions as in theorem [2] to obtain the following general result. Theorem 5 Suppose that the common inter-cluster coupling condition ([7|) is satisfied. For a bi- directed unweighted graph Q, there exist positive weights to the graph Q such that Ineq. ( [27\i holds if and only if all vertices in the same cluster belongs to the same connected component in the graph Q. In fact, the proofs of theorems |4] and [5] simply repeats those of theorems [Hand [21 respectively. Ref. [26] is a paper closely relating to this paper. Here, we give some comparisons. First, investigated the local cluster synchronization of inter-connected clusters by extending the master 20 stability function method. Instead, in this paper, we are concerned with the global cluster synchro- nization. Second, the models discussed are different. The topologies discussed in ll26ll exclude intra-cluster couplings. In this paper, we consider more general graph topology. Third, Ref. n2oi\ studied the situation of nonlinear coupling function and we consider the linear case. Despite that Ref. [26] considered different coupling stengths for clusters and we consider a common one in Sec. II, theorem|4]can apply to discussion of such models proposed in Ref. ll26ll . V. CONCLUSIONS The idea for studying synchronization in networks of coupled dynamical systems sheds light on cluster synchronization analysis. In this paper, we study cluster synchronization in networks of coupled non-identical dynamical systems. Cluster synchronization manifold is defined as that the dynamics of the vertices in the same cluster are identical. The criterion for cluster synchronization is derived via linear matrix inequality. The differences between clustered dynamics are guaranteed by the non-identical dynamical behaviors of different clusters. The algebraic graph theory tells that the communicability between each pair of vertices in the same cluster is a doorsill for chaos cluster synchronization. This leads an description of two schemes to realize cluster synchronization: self- organization and driving. One can see that the latter scheme implies that cluster synchronization can be realized in a non-clustered networks, for example, the graph 2 in the Fig. [IJ Adaptive feedback algorithm is used to enhance cluster synchronization motions. Acknowledgments This work was jointly supported by the National Natural Sciences Foundation of China under Grant Nos. 60774074 and , the Mathematical Tian Yuan Youth Foundation of China No. 10826033, and SGST 09DZ2272900. Appendix In this appendix, for each positive d, we give the details to find au E Tcil) with u ^ such that u^DLu = in the case that there exists a cluster Ci that does not belong the same connected 21 component. Without loss of generality, suppose L has form: Li L2 Let Vi and V2 corresponds the sub-matrices Li and L2 respectively. And, Ci P Vj 7^ for all i = 1,2. We consider two situations. First, in the case that Ci is isolated from other clusters. In other words, there are no edges between Ci and other clusters. Let a i e CiflVi otherwise Let a — X^jgCi nvi ^ ~ Z^jeCi ni^2 Then, if picking a and /3 satisfying aa + bp — with a,f3 y^O, then e 72^(1) holds. In addition, vJDLu = due to Lu = 0. In the case that Ci is not isolated, suppose there are totally K clusters, and Li and L2 are both connected (otherwise, we only consider the connection parts of Li and L2 that contain vertices from Ci), due to the common inter-cluster coupling condition, and the absence of isolated cluster. we have d fl holds for all i with 1, • • • ,K and j — 1, 2. Pick a vector u — [ui, ak i eCkf]Vi Denote ^ = Eiec^ n Vi 4 = S^iGC^ n V2 ^^i = [ai, • • • , (^kV, U2 = • • • , PkV, u = [uj , mJ]^, Di = diag[(ij, ■ ■ ■ , d]^], D2 = diagfc?^, ■ ■ ■ , dj^], and L> = diag[Z)i, D2]. Define a K X K matrix W'^ from Li in such way that for i ^ j, W^j = 1 if there's interaction between K cluster i and j, and Wl^ — otherwise. Wl^ — — Yl, ^Ij- Define W"^ in the same way according to L2, due to the common inter-cluster condition, it is easy to see that — W'^. Denote - diag[iy\ 2] _ After computation, we have that for any given positive definite diagonal matrix D = diag[(ii, ■ ■ ■ , dm], u^DLu = u^DWu holds. For u E T^, U2 = —DiD2^ui. Denote v = DiUi, we have u DWu \V V ]WD- Ir^T^TlT — v^W^{D]^^ + D2^)v. This implies that if we can find V satisfying v^W^{D^^ + D2^)v — 0, then there exists u e TeO) such that vJDLu — 0. Since W^{D]^^ + -D^^) has rank at most X — 1, we can pick v as the eigenvector corresponding to the zero eigenvalue of W^{D^^ + D^^), and this completes the proof. 22 In summary, in both situations, we can find certain nonzero vector u belonging to the transverse space 72^(1) and u^DLu = 0. [1] A. Pikovsky, M. Roseblum, J. Kurths, Synchronization: A universal concept in nonlinear sciences ( Cambridge University Press, 2001). [2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, "Complex networks: structure and dynamics", Phys. Rep., 424, 175 (2006). [3] X. F. Wang, G. Chen, "Complex networks: small-world, scale-free and beyond", IEEE Circ. Syst. Mag., 3:1, 6 (2003). [4] H. Fujisaka, T. Yamada, Prog. Theor. Phys., 69, 32 (1983); 72, 885 (1984); V. S. Afraimovich, N. N. Verichev, M. I. Rabinovich, Izv Vyssh. Uchebn. Zaved. Radiofiz., 29, 795 (1986). [5] S. H. Strogatz, 1. Stewart, Sci. Amer., 269:6, 102 (1993). [6] C. M. Gray J. Comput. Neurosci., 1:11, 38 (1994). [7] L. Glass, Nature, 410, 277 (2001). [8] S. Boccaletti, J. Kurths, G. Osipov, D. L. Valladares, C. S. Zhou, Phys. Rep., 366, 1 (2002). [9] L. M. Pecora, T. L. Carroll, Phys. Rev Lett., 64:8, 821 (1990); J. F. Heagy, T. L. Carroll, L. M. Pecora, Phys. Rev. E., 50, 1874 (1994). [10] P. Ashwin, J. Buescu, I. Stewart, Nonlinearity 9 703 (1996). [11] J. Jost, M. P Joy, Phys. Rev. E, 65, 016201 (2001); X. F. Wang, G. Chen, IEEE Trans. Circ. Syst.-l, 49:1, 54 (2002); G. Rangarajan, M. Ding: Phys. Lett. A, 296, 204 (2002); Y. H. Chen, G. Rangarajan, and M. Ding: Phys. Rev E., 67, 026209 (2003). [12] C. W. Wu, L. O. Chua, IEEE Trans. Circ. Syst.-l, 42:8, 430 (1995). [13] I. V. Belykh, V. N. Belykh, M. Hasler, Physica D, 195, 159 (2004) and 188 (2004);J. Cao, R Li, W. Wang, Phys. Lett. A, 353, 318 (2006). [14] W. Lu, T. Chen, Physica D, 213, 214 (2006). [15] C. W. Wu, Nonlinearity, 18, 1057 (2005). [16] A. Schnitzler, J. Gross, Nat. Rev. Neurosci, 6, 285 (2005). [17] P. R. Chandler, M. Patcher, S. Rasmussen, Proceedings of the American Control Society, 20 (2001); K. M. Passino, IEEE Control Syst. Mag., 22, 52 (2002); J. Finke, K. Passino, A. G. Sparks, EEEE Control Syst. Mag., 14, 789 (2006). 23 [18] B. Blasius, A. Huppert, L. Stone, Nature (London), 399, 354 (1999); E. Montbrio, J. Kurths, B. Blasius, Phy. Rev. E, 70, 056125 (2004). [19] N. F. Rulkov, Chaos, 6, 262 (1996). [20] L. Stone, R. Olinky, B. Blasius, A. Huppert, B. Gazelles, Proceedings of the Sixth Experimental Chaos Conference, AIP Conf. Proc. No. 662, 476 (2002). [21] E. Jones, B. Browning, M. B. Dias, B. Argall, M. Veloso, A. Stentz, Proceedings IEEE International Conference on Robotics and Automation, Orlando, 2006, 570-575; K. -S, Hwang, S. -W. Tan, C. -C. Chen, IEEE Trans. Fuzzy Syst., 12, 569 (2004). [22] V. N. Belykh, 1. V. Belykh, M. Hasler, Phy Rev. E, 62, 6332 (2000); V. N. Belykh, 1. V. Belykh, E. Mosekilde, Phys. Rev. E, 63 036216 (2001). [23] Z. Ma, Z. Liu, G. Zhang, Chaos, 16, 023103 (2006). [24] W. Wu, T. Chen, Physica D, 238, 355 (2009); W. Wu, W. Zhou, T. Chen, IEEE T. Circuits Syst.-I, in press, (2008); [25] S. Jalan, R. E. Amritkar, Pys. Rev. Lett., 90:1, 014101 (2003); S. Jalan, R. E. Amritkar, C.-K. Hu, Phys. Rev. E, 72, 016211 (2005); 016212 (2005). [26] F. Sorrentino, E. Ott, Phys. Rev. E, 76, 056114 (2007). [27] L. Chen, J. Lu, J. Syst. Sci. Complexity, 20, 21 (2008). [28] 1. V. Belykh, V. N. Belykh, M. Hasler, Chaos, 13:1, 165 (2003). [29] Q.-C. Pham, J.-J. Slotine, Neural Networks, 20, 62 (2007). [30] W. Lohmiller, J.-J. Slotine, Automatica, 34:6, 671 (1998). [31] "Special issue on nonlinear waves, patterns, and spatiotemporal chaos in dynamical arrays", edited by L. O. Chua, IEEE Trans. Circ. Syst., 42 (1995). [32] P. A. Horn, C. R. Johnson, Matrix Analysis (Cambridge University Press, New York, 1985). [33] J. P Lasalle, IRE Trans. Circuit Theory 7, 520 (1960). [34] M. Chavez, D.-U. Hwang, H. G. E. Hentschel, S. Boocaletti, Phys. Rev. Lett., 94, 218701 (2005); C. Zhou, J. Kurths, Phys. Rev. Lett., 96, 164102 (2006); S. Boccaletti, D.-U. Hwang, M. Chavez, A. Amann, J. Kurths, L. M. Pecora, Phys. Rev. E, 74, 016102 (2006); C. S. Zhou, A. E. Motter, J. Kurths, Phys. Rev. Lett., 96, 034101 (2006). [35] X. Liu, T Chen, Physica D, 237, 630 (2008). [36] J. Lu, J. Cao, Chaos, 15, 043901 (2005); D. Huang, Phys. Rev. E, 71, 037203 (2005); J. Zhou, J-A. Lu, J. Lii, IEEE Trans. Automatic Control, 51:4, 652 (2006); W. Lu, Chaos, 17, 023122 (2007). 24 [37] The reason why we choose initial time for average from 50 not is that even if the coupled system synchronizes clustering, the variance as calculated by var can be very large (> 10"^). This implies that it will take a very long time for average to make the variance is near zero. To save calculationg amount, we pick the inital time apart from zero. [38] Our theoretical result (proposition [T]) can only intepret the case the coupled system can clustering synchronize if the coupling strength c is large enough. As shown by Fig. |2l the coupled system dTOl l over the graphs 2 and 3 can clustering synchronize only if the coupling strength c is greater than some threshold. But, for the graph 1, despite the coupled system can synchronize if c is greater than some value (around 10), there exists an interval (about [2.2, 5]) of c by which the system synchronizes. This can not be interpreted via our theoretical result. [39] Connected component in a direct graph Q is a. maximal vertex set of which each vertices can access all others. [40] Since these theoretical estimation is rather loose, we use computer-aided method to get the estimation 25 12 3 4 FIG. 1: Graphs of examples. In the graph 1, the white cluster (vertex set 1 — 3) is driven since they has no intra-cluster edges, the red cluster (vertex set 4— 7) is mixed since each pari of vertices can access each other via only inter- or intra- edges, and the blue cluster is driven since each pair of vertices can access each other via only the inter-cluster edges but can not communicate only via intra-cluster edges. In the graph 2, each cluster of the white and blue clusters (vertex sets 1 — 4 and 9 — 12) is driven since each pair of vertices can access each other only via inter-cluster edges but only has a single intra-cluster edges. However, the read cluster (vertex set 5 — 8) is recognized as a hybrid cluster since the sets of inter- or intra-cluster edges are both necessary for communication between each pair of vertices. In the graph 3, the red and blue clusters (vertex sets 5 — 8 and 9 — 12) are all driven since they do not have intra-cluster edges and the white cluster (vertex set 1 — 4) is an example of self-organization since each pair of vertices can communicate via only the intra-cluster edges but can not if removing the intra-cluster edges. 26 1500r CO > c 1500 1 , , c FIG. 2: var with respect to c : (a) for the graph 1; (b) for the graph 2; (c) for the graph 3, respectively. 27 200 2 4 6 8 10 12 14 16 18 20 time 200 2 4 6 8 10 12 14 16 18 20 time . 3: Dynamics of dis{t) through Eq. (ITOl ): (a) for the graph 1 with c = 12; (b) for the graph 2 with 25; (c) for the graph 3 with c = 20, respectively. 28 FIG. 4: Phase dynamics for each cluster through equahty (fTOl) : (a) xi — X2 phase dynamics for each cluster in the graph 1; (b) X2 — X3 phase dynamics for each cluster in the graph 2; (2) X3 — xi phase dynamics for each cluster in the graph 3, respectively. 29 10 20 30 40 50 60 70 80 time 5 10 15 20 25 30 35 40 45 50 time FIG. 5: Dynamics of the logarithm of K{t) through equality (flOl ) with the adaptive algorithm (l20l) : (a) for the graph 1; (b) for the graph 2; (c) for the graph 3, respectively. 30 31 32 FIG. 8: Two sets of the final weighted topologies of the three graphs in Fig. [Uvia employing the adaptive algorithm (l20l ) with two different sets of initial data but the same parameters. Set A and B correspond two set of initial values and (a)-(c) correspond the graph 1-3 in Fig. [T] The color of the line represents the sign of the weights (black for positive and gray for negative) and the width of the line represents the scale of the weight in modulus. 33